class Solution(object):
    def findReplaceString(self, s, indices, sources, targets):
        t_list = []
        n = len(s)
        m = len(indices)
        t = [[indices[i], sources[i], targets[i]] for i in range(m)]
        t.sort()
        indices, sources, targets = [z[0] for z in t], [z[1] for z in t], [z[2] for z in t]
        last_index = 0
        for i in range(m):
            index = indices[i]
            if index > last_index:
                t_list.append(s[last_index:index])
            if index + len(sources[i]) <= n and s[index: index + len(sources[i])] == sources[i]:
                t_list.append(targets[i])
                last_index = index + len(sources[i])
            else:
                last_index = index
        if last_index < n:
            t_list.append(s[last_index:])
        return ''.join(t_list)


data = Solution()
s = "vmokgggqzp"
indices = [3, 5, 1]
sources = ["kg", "ggq", "mo"]
targets = ["s", "so", "bfr"]
print(data.findReplaceString(s, indices, sources, targets))
